package _01_第一季.树04.Tree03;

import javax.management.relation.Role;
import java.util.Comparator;

public class RBTree<E> extends BBST<E>{
    //红黑树颜色节点的定义 红为假  黑为真
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    public RBTree(){
        this(null);
    }

    public RBTree(Comparator<E> comparator){
        super(comparator);
    }

    //红黑树内部节点类
    private static class RBNode<E> extends Node<E>{
        boolean color = RED; //节点默认是红色,在添加节点的时候能更快的满足红黑树性质
        public RBNode(){
            this(null,null);
        }
        public RBNode(E element,Node<E> parent){
            super(element, parent);
        }
        @Override
        public String toString() {
            String str = "";
            if(color == RED){
                str = "R_";
            }
            return str+element.toString();
        }
    }

    /**
     * RBTree添加节点，共有12种情况，默认新添加的节点颜色为红色
     * 1.4种新添加的节点父节点为黑色，满足红黑树的5条性质，不处理
     * 2.4种不上溢的情况，但是父节点是红色(双红)，有LL/RR,LR/RL，判定条件是叔父节点不是红色
     *   对于LL/RR的情况，要对祖父节点进行左旋转或者右旋转，同时将父节点染成黑色，祖父节点染成红色
     *   对于LR/RL的情况，要对父节点进行左旋转或右旋转，在对祖父节点进行左旋转或者右旋转，将待添加节点染成黑色，祖父节点染成红色
     * 3.4种添加后产生上溢的情况，判定条件是叔父节点是红色；
     *   这时，将父节点和叔父节点染成黑色节点，各自分裂，将祖父节点染成红色向上合并，当成一个新添加的节点进行递归处理
     *   可能向上合并后，还会产生上溢现象，会持续到根节点，所以到达根节点将其染成黑色即可
     *
     * @param node 新添加的节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;
        if(parent == null){
            black(node);
            return;
        }

        if(isBlack(parent)) return;

        Node<E> grand = parent.parent;
        Node<E> uncle = parent.sibling();

        if(isRed(uncle)){
            black(parent);
            black(uncle);
            afterAdd(red(grand));
            return;
        }

        if(parent.isLeftChild()){
            red(grand);
            if(node.isLeftChild()){
                black(parent);
            }else{
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{
            red(grand);
            if(node.isLeftChild()){
                black(node);
                rotateRight(parent);
            }else{
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     *
     * @param node 待删除的节点或用于取代的节点
     *
     */
    @Override
    protected void afterRemove(Node<E> node) {
        //删除红色子节点或删除有一个红色子节点的黑色节点
        //红色子节点马上就要删除，染黑也没关系
        //有一个红色子节点的黑色节点将其染黑返回即可
        if(isRed(node)){
            black(node);
            return;
        }

        Node<E> parent = node.parent;
        if(parent==null) return;

        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;

        if(left){
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                sibling = parent.right;
            }

            if(isBlack(sibling.left) && isBlack(sibling.right)){
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                if(isBlack(sibling.right)){
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.right);
                rotateLeft(parent);
            }

        }else{
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;
            }

            if(isBlack(sibling.left) && isBlack(sibling.right)){
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if(parentBlack){
                    afterRemove(parent);
                }

            }else{
                if(isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling,colorOf(parent));
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }
        }
    }

    /**
     * 对节点染色的方法
     * @param node 待染色的节点
     * @param color 颜色
     * @return 返回染色后的节点
     */
    private Node<E> color(Node<E> node,boolean color){
        if(node == null) return null;
        ((RBNode<E>)node).color = color;
        return node;
    }

    /**
     * 将节点染成红色
     * @param node 带染色的节点
     * @return 返回染成红色的节点
     */
    private Node<E> red(Node<E> node){
        return color(node,RED);
    }

    /**
     * 将节点染成黑色
     * @param node 带染色的节点
     * @return 返回染成黑色的节点
     */
    private Node<E> black(Node<E> node){
        return color(node,BLACK);
    }

    /**
     * 判断节点颜色的方法
     * @param node
     * @return 返回节点的颜色
     */
    private boolean colorOf(Node<E> node){
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    //判断节点颜色是否是红色
    private boolean isRed(Node<E> node){
        return colorOf(node) == RED;
    }

    //判断节点颜色是否是黑色
    private boolean isBlack(Node<E> node){
        return colorOf(node) == BLACK;
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element,parent);
    }
}
